home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 401-425 / disk_419 / yacc / src.lzh / Src / warshall.c < prev    next >
C/C++ Source or Header  |  1990-07-14  |  1KB  |  85 lines
  1. #include "defs.h"
  2.  
  3. transitive_closure(R, n)
  4. unsigned *R;
  5. int n;
  6. {
  7.     register int rowsize;
  8.     register unsigned mask;
  9.     register unsigned *rowj;
  10.     register unsigned *rp;
  11.     register unsigned *rend;
  12.     register unsigned *ccol;
  13.     register unsigned *relend;
  14.     register unsigned *cword;
  15.     register unsigned *rowi;
  16.  
  17.     rowsize = WORDSIZE(n);
  18.     relend = R + n*rowsize;
  19.  
  20.     cword = R;
  21.     mask = 1;
  22.     rowi = R;
  23.     while (rowi < relend)
  24.     {
  25.     ccol = cword;
  26.     rowj = R;
  27.  
  28.     while (rowj < relend)
  29.     {
  30.         if (*ccol & mask)
  31.         {
  32.         rp = rowi;
  33.         rend = rowj + rowsize;
  34.         while (rowj < rend)
  35.             *rowj++ |= *rp++;
  36.         }
  37.         else
  38.         {
  39.         rowj += rowsize;
  40.         }
  41.  
  42.         ccol += rowsize;
  43.     }
  44.  
  45.     mask <<= 1;
  46.     if (mask == 0)
  47.     {
  48.         mask = 1;
  49.         cword++;
  50.     }
  51.  
  52.     rowi += rowsize;
  53.     }
  54. }
  55.  
  56. reflexive_transitive_closure(R, n)
  57. unsigned *R;
  58. int n;
  59. {
  60.     register int rowsize;
  61.     register unsigned mask;
  62.     register unsigned *rp;
  63.     register unsigned *relend;
  64.  
  65.     transitive_closure(R, n);
  66.  
  67.     rowsize = WORDSIZE(n);
  68.     relend = R + n*rowsize;
  69.  
  70.     mask = 1;
  71.     rp = R;
  72.     while (rp < relend)
  73.     {
  74.     *rp |= mask;
  75.     mask <<= 1;
  76.     if (mask == 0)
  77.     {
  78.         mask = 1;
  79.         rp++;
  80.     }
  81.  
  82.     rp += rowsize;
  83.     }
  84. }
  85.